package puzzle.projecteuler.p200;

import java.util.ArrayList;
import java.util.List;

import astudy.util.Combination;



public class Problem106B {

	/**
	 * 1. For a set, whose size is n, there are exactly (3^n+1)/2 - 2^n subset pairs,
	 * each pairs are disjoint.
	 * 
	 * 2. For a set, whose size is n, there are exactly X_n subset pairs,
	 * each pairs are disjoint and with same size.
	 * Here, X_n is the coefficient of X^n in (1+x+x^2)^n 
	 * 
	 * 3. Two non-empty disjoint sets B and C should be tested, must satisfied 
	 * conditions below:
	 * 1) |B| = |C|
	 * 2) suppose A = {a_1, ... , a_n}, a_1<...<a_n.
	 * B = {a_i_1, ..., a_i_s}, C = {a_j_1, ..., a_j_s} and i_1 < j_1
	 * then at least one of the inequality can be true:
	 * 		i_2 < j_2
	 * 		...
	 * 		i_s < j_s
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		List<List<Integer>> subsets = getSubsets(12);
		int count = 0;
		for (int i = 0; i < subsets.size(); i ++) {
			for (int j = i+1; j < subsets.size(); j ++) {
				if (needTest(subsets.get(i), subsets.get(j))) {
//					System.out.println(subsets.get(i));
//					System.out.println(subsets.get(j));
					count ++;
				}
			}
		}
		System.out.println(count);
	}
	
	/**
	 * 测试集合a,b 是否需要test
	 * @param a
	 * @param b
	 * @return
	 */
	private static boolean needTest(List<Integer> a, List<Integer> b) {
		
		if (a.size() != b.size()) {
			return false;
		} else {
			//check 'disjoint'
			for (Integer t: a) {
				if (b.contains(t)) {
					return false;
				}
			}
			//check 'need test'
			int c1 = 0;
			int c2 = 0;
			for (int i = 0; i < a.size(); i ++) {
				if (a.get(i) < b.get(i)) {
					c1 ++;
				} else if (a.get(i) > b.get(i)) {
					c2 ++;
				} else {
					return false;
				}
			}
			return (c1 != 0 && c2 != 0);
		}
	}

	/**
	 * 返回n元集合的所有子集。这里用下标表示子集。
	 * @param n
	 * @return
	 */
	private static List<List<Integer>> getSubsets(int n) {

		int[] indexes = new int[n];
		for (Integer i = 0; i < indexes.length; i ++) {
			indexes[i] = 0;
		}
		List<List<Integer>> subsets = new ArrayList<List<Integer>>();
		while ((indexes = Combination.next(n+1, indexes)) != null) {
			List<Integer> tmp = new ArrayList<Integer>();
			for (Integer i = 0; i < indexes.length; i++) {
				if (indexes[i] != 0) {
					tmp.add(indexes[i]-1);
				}
			}
			subsets.add(tmp);
		}
		return subsets;
	}
}
